#include <iostream>
using namespace std;

struct BiNode {
    int data;
    BiNode *lchild, *rchild;
};

typedef BiNode *BiTree;

BiTree Create()
{ 
    int e;
    cin >> e;
    if (e == 0)
        return nullptr;
    else
        return new BiNode { e, Create(), Create() };
}

void Destroy(BiTree T)
{
    if(T) {
        Destroy(T->lchild);
        Destroy(T->rchild);
        delete T;
    }
}

template <typename F>
void PreOrder(BiTree T, F visit)
{
    if(T) {
        visit(T->data);
        PreOrder(T->lchild, visit);
        PreOrder(T->rchild, visit);
    }
}

template <typename F>
void InOrder(BiTree T, F visit)
{
    if(T) {
        InOrder(T->lchild, visit);
        visit(T->data);
        InOrder(T->rchild, visit);
    }
}

template <typename F>
void PostOrder(BiTree T, F visit)
{
    if (T) {
        PostOrder(T->lchild, visit);
        PostOrder(T->rchild, visit);
        visit(T->data);
    }
}

void print(int e) { cout << e << ' '; }

int main()
{
    auto T = Create();
    cout << "PreOrder: ";
    PreOrder(T, print);
    cout << endl;

    cout << "InOrder: ";
    InOrder(T, print);
    cout << endl;

    cout << "PostOrder: ";
    PostOrder(T, print);
    cout << endl;

    Destroy(T);
    return 0;
}

